package com.JAVA程序员面试宝典;

/**
 * 实现类似jdk中LinkedList类的功能
 * 支持从头结点插入和删除，查找操作
 * @author qiuxiaochen
 */
public class 实现LinkedList {
	private class Data {
		private Object object;
		private Data next = null;

		public Data(Object object) {
			this.object = object;
		}
	}

	private Data first = null;

	public void insertFirst(Object obj) {
		Data data = new Data(obj);
		data.next = first;
		first = data;
	}

	public Object deleteFirst() {
		if (first == null) {
			System.out.println("The stack is empty!!");
			return null;
		} else {
			first = first.next;
			return first.object;
		}
	}

	public Object find(Object obj) {
		if (first == null) {
			System.out.println("The stack is empty!!");
			return null;
		} else {
			Data cur = first;
			while (cur != null) {
				if (cur.object.equals(obj)) {
					return cur.object;
				}
				cur = cur.next;
			}
			return null;
		}
	}

	public void delete(Object obj) {
		if (first == null) {
			System.out.println("The stack is empty!!");
			return;
		}
		while (first.object.equals(obj)) {
			first = first.next;
		}
		Data pre = first;
		Data cur = first.next;
		while (cur != null) {
			if (cur.object.equals(obj)) {
				pre.next = cur.next;
				cur = cur.next;
				continue;
			}
			pre = cur;
			cur = cur.next;
		}
	}

	public void display() {
		if (first == null) {
			System.out.println("The stack is empty!!");
		} else {
			Data cur = first;
			while (cur != null) {
				if (cur.next == null)
					System.out.print(cur.object);
				else
					System.out.print(cur.object + "---->");
				cur = cur.next;
			}
		}
	}

	public static void main(String[] args) {
		实现LinkedList linkedList = new 实现LinkedList();
		linkedList.insertFirst(1);
		linkedList.insertFirst(1);
		linkedList.insertFirst(2);
		linkedList.insertFirst(2);
		linkedList.insertFirst(3);
		linkedList.insertFirst(13);
		linkedList.insertFirst(23);
		linkedList.insertFirst(23);
		linkedList.display();
		System.out.println();
		System.out.println(linkedList.find(1));
		linkedList.delete(1);
		linkedList.delete(23);
		linkedList.display();
	}
}
